// 力扣143：重排链表

// 给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
// 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
// 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

void reverse_list(struct node *head)
{
	struct node *pre = NULL, *cur = head, *save;
	while (cur) {
		save = cur->next;
		cur->next = pre;

		pre = cur;
		cur = save;
	}
	head = pre;
}

struct node *find_mid_node(struct node *head)
{
	struct node *slow, *fast;
	slow = fast = head;
	while (fast) {
		fast = fast->next;
		if (fast) {
			fast = fast->next;
			slow = slow->next;
		}
	}
	return slow;
}

// 解题思路：
// 	首先找到链表的中间位置，从其后面拆开分成两半，保存要反向插入的后半部分的首节点，并把前半部分的最后一个节点的next指针置为NULL
// 	然后将后半部分链表反转，并保存反转后新链表的首节点
// 	最后从反转后的链表首节点开始，依次间隔一个位置插入到前半部分链表中
void reorder_list(struct node *head)
{
	struct node *mid, *A = head, *B;
	mid = find_mid_node(head);
	B = mid->next;
	mid->next = NULL;
	reverse_list(B);
	
	struct node *save;
	while (A) {
		save = A->next;
		A->next = B;
		B = B->next;
		A->next->next = save;
		A = save;
	}
}
